home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / djgpp / src / libgplus.5 / libgplus / etc / adt-exam / kmp.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1991-06-28  |  10.9 KB  |  311 lines
  1. //From: "Douglas C. Schmidt" <schmidt@zola.ICS.UCI.EDU>
  2. //Date: Fri, 28 Jul 89 11:47:11 -0700
  3.  
  4. /* Nifty little program that illustrates an implementation of the Knuth, 
  5.    Morris, Pratt string matching algorithm.
  6.  
  7.    This program has a user interface similar to fgrep, i.e., when
  8.    you provide it with a fixed pattern it prints out all the lines
  9.    from the standard input (or one user-specified input file) that 
  10.    contain at least one substring that matches the provided pattern. 
  11.    
  12.    Relevant options are:
  13.    
  14.    -i: Ignore case when performing comparisons. 
  15.    -n: Print out lines numbers along with the matching lines.
  16.    -v: Print out lines that *don't* match the pattern.
  17.  
  18.    The code below is extensively commented.  If these comments
  19.    distract you, run the code through g++ -E first ;-). */
  20.    
  21. #include <stdio.h>
  22. #include <std.h>
  23. #include <GetOpt.h>
  24.  
  25. /* This array is designed for mapping upper and lower case letter
  26.    together for a case independent comparison.  The mappings are
  27.    based upon the ASCII character sequences. */
  28. char charmap[] = 
  29. {
  30.     '\000', '\001', '\002', '\003', '\004', '\005', '\006', '\007',
  31.     '\010', '\011', '\012', '\013', '\014', '\015', '\016', '\017',
  32.     '\020', '\021', '\022', '\023', '\024', '\025', '\026', '\027',
  33.     '\030', '\031', '\032', '\033', '\034', '\035', '\036', '\037',
  34.     '\040', '\041', '\042', '\043', '\044', '\045', '\046', '\047',
  35.     '\050', '\051', '\052', '\053', '\054', '\055', '\056', '\057',
  36.     '\060', '\061', '\062', '\063', '\064', '\065', '\066', '\067',
  37.     '\070', '\071', '\072', '\073', '\074', '\075', '\076', '\077',
  38.     '\100', '\141', '\142', '\143', '\144', '\145', '\146', '\147',
  39.     '\150', '\151', '\152', '\153', '\154', '\155', '\156', '\157',
  40.     '\160', '\161', '\162', '\163', '\164', '\165', '\166', '\167',
  41.     '\170', '\171', '\172', '\133', '\134', '\135', '\136', '\137',
  42.     '\140', '\141', '\142', '\143', '\144', '\145', '\146', '\147',
  43.     '\150', '\151', '\152', '\153', '\154', '\155', '\156', '\157',
  44.     '\160', '\161', '\162', '\163', '\164', '\165', '\166', '\167',
  45.     '\170', '\171', '\172', '\173', '\174', '\175', '\176', '\177',
  46.     '\200', '\201', '\202', '\203', '\204', '\205', '\206', '\207',
  47.     '\210', '\211', '\212', '\213', '\214', '\215', '\216', '\217',
  48.     '\220', '\221', '\222', '\223', '\224', '\225', '\226', '\227',
  49.     '\230', '\231', '\232', '\233', '\234', '\235', '\236', '\237',
  50.     '\240', '\241', '\242', '\243', '\244', '\245', '\246', '\247',
  51.     '\250', '\251', '\252', '\253', '\254', '\255', '\256', '\257',
  52.     '\260', '\261', '\262', '\263', '\264', '\265', '\266', '\267',
  53.     '\270', '\271', '\272', '\273', '\274', '\275', '\276', '\277',
  54.     '\300', '\341', '\342', '\343', '\344', '\345', '\346', '\347',
  55.     '\350', '\351', '\352', '\353', '\354', '\355', '\356', '\357',
  56.     '\360', '\361', '\362', '\363', '\364', '\365', '\366', '\367',
  57.     '\370', '\371', '\372', '\333', '\334', '\335', '\336', '\337',
  58.     '\340', '\341', '\342', '\343', '\344', '\345', '\346', '\347',
  59.     '\350', '\351', '\352', '\353', '\354', '\355', '\356', '\357',
  60.     '\360', '\361', '\362', '\363', '\364', '\365', '\366', '\367',
  61.     '\370', '\371', '\372', '\373', '\374', '\375', '\376', '\377',
  62. };
  63.  
  64. /* The list of available program options. */
  65. enum options
  66. {
  67.   DEBUG, FOLD_CASE, LINE_NUMBERS, INVERSE, OPTION_SIZE
  68. };
  69.  
  70. /* Vector storing the enabled options (all initially disabled). */
  71. char option[OPTION_SIZE];
  72.  
  73. /* Data and function members necessary to implement the KMP algorithm. */
  74. class kmp
  75. {
  76. private: 
  77.  
  78. #ifdef GNUG
  79.   const int RESET_PATTERN_FLAG = -1;
  80. #else
  81. #define RESET_PATTERN_FLAG -1
  82. #endif  
  83.  
  84.   int  *fail_trans_table; /* Stores the generated nfa used when matching. */
  85.   char *pattern;          /* Stores the user-supplied pattern. */
  86.   int   pattern_len;      /* Pattern length. */
  87.  
  88.   void print_fail_trans_table (void);
  89.  
  90. public:
  91.   kmp (char *pattern, int pattern_len, int debug = 0);
  92.  ~kmp () { delete fail_trans_table; }
  93.   int operator ()(char *text, int text_len);
  94. };
  95.  
  96. /* Provide a debugging dump of the failure function.  Nothing fancy... */
  97.  
  98. void
  99. kmp::print_fail_trans_table (void)
  100. {
  101.   int i;
  102.   
  103.   for (i = 0; i < pattern_len; i++)
  104.     printf ("%3d,", i);
  105.  
  106.   putchar ('\n');
  107.  
  108.   for (i = 0; i < pattern_len; i++)
  109.     printf ("%3d,", fail_trans_table [i]);
  110.  
  111.   putchar ('\n');
  112. }
  113.  
  114. /* This constructor builds the transition table that encodes the failure function 
  115.    automaton.  The table stores the PATTERN index we go to in the event of a 
  116.    mismatch with the input text string.  This generation process runs in time 
  117.    linear to the pattern size. 
  118.    
  119.    The terms SUFFIX and PREFIX used below are defined in terms of each other.  
  120.    That is, at each state of the failure function we seek to determine the largest 
  121.    pattern prefix that matches with the largest suffix in the actual input text.  
  122.    This information informs us how far we can legitimately shift the pattern to the 
  123.    right when a mismatch occurs during the string matching process. 
  124.    
  125.    Stated more formally, this means that for all i (0 <= i <= (PATTERN_LEN - 1))
  126.    FAIL_TRANS_TABLE (i) is the largest j < i, such that PATTERN[1..j - 1] 
  127.    is a suffix of PATTERN[1..i - 1] and PATTERN[i] != PATTERN[j]. */
  128.  
  129. kmp::kmp (char *pat, int len, int debug):
  130.   pattern (pat), fail_trans_table (new int[len]), pattern_len (len)
  131. {
  132.   /* Points 1 beyond the rightmost potential *suffix* in the pattern (which is 
  133.      actually simulating the behavior of an actual input text string. */
  134.   int suffix_end = 0;
  135.  
  136.   /* Points 1 beyond the rightmost potential *prefix* in the pattern. */
  137.   int prefix_end = fail_trans_table[suffix_end] = RESET_PATTERN_FLAG;
  138.   
  139.   do
  140.     {
  141.       /* This WHILE loop uses the precomputed failure function to look further 
  142.          left into the pattern trying to find an index location where the pattern 
  143.          prefix matches the pattern suffix.  However, if/when we locate the
  144.          RESET_PATTERN_FLAG this means that we can just skip ahead to the next 
  145.          character in the input text. */
  146.          
  147.       while (prefix_end != RESET_PATTERN_FLAG 
  148.              && pattern[suffix_end] != pattern[prefix_end])
  149.         prefix_end = fail_trans_table[prefix_end];
  150.  
  151.       /* Once SUFFIX_END and PREFIX_END are pre-incremented below we know that 
  152.          the first PREFIX_END characters of PATTERN match the characters in 
  153.          positions PATTERN[SUFFIX_END - PREFIX_END .. SUFFIX_END - 1], i.e.,
  154.          the last PREFIX_END characters in the rightmost part of the first 
  155.          SUFFIX_END - 1 characters in PATTERN.
  156.         
  157.          If the character at location PATTERN[SUFFIX_END] matches that at 
  158.          PATTERN[PREFIX_END] it is silly to have the failure transition
  159.          jump to that pattern location (since it would immediately fail to
  160.          match, of course!). Instead, in that case we just ``borrow'' the
  161.          previously computed transition stored at FAIL_TRANS_TABLE[PREFIX_END]
  162.          and use it. */
  163.  
  164.       if (pattern[++suffix_end] == pattern[++prefix_end])
  165.         fail_trans_table[suffix_end] = fail_trans_table[prefix_end];
  166.       else
  167.         fail_trans_table[suffix_end] = prefix_end;
  168.     }
  169.   /* Adding the extra 1 here is necessary since C strings are
  170.      indexed from 0 to pattern_len - 1... */
  171.  
  172.   while (suffix_end + 1 < pattern_len);
  173.  
  174.   if (debug)
  175.     print_fail_trans_table ();
  176. }
  177.  
  178. /* Actually perform the KMP matching algorithm using the generated determinisitic 
  179.    pattern matching match encoded in the failure transition table.  This version 
  180.    is optimized on the assumption that there will be more characters in the text 
  181.    input that *don't* match the pattern than ones that do match it. Therefore, we 
  182.    make a special effort to keep looping through the failure function as long as 
  183.    the text and pattern don't match. */
  184.  
  185. int
  186. kmp::operator ()(char *text, int text_len)
  187. {
  188.   int suffix_end = RESET_PATTERN_FLAG;
  189.   int prefix_end = RESET_PATTERN_FLAG;
  190.  
  191.   /* If TEXT length is shorted than PATTERN we'll bail out now... */
  192.   if (text_len < pattern_len)
  193.     return 0;
  194.     
  195.   /* Split the following two cases so that we don't pay any
  196.      unnecessary overhead when case folding is not required. */
  197.   if (option[FOLD_CASE])
  198.   
  199.   /* Note how this main loop is almost identical with the 
  200.      `failure transition table building' algorithm used above. */
  201.  
  202.     do
  203.       {
  204.         /* Ignore case when matching and keep applying the failure function
  205.            until we get a match or are forced to restart the pattern (starting
  206.            with the *following* input text character, that is). */
  207.  
  208.         while (prefix_end != RESET_PATTERN_FLAG 
  209.                && charmap[text[suffix_end]] != charmap[pattern[prefix_end]])
  210.           prefix_end = fail_trans_table[prefix_end];
  211.  
  212.         if (prefix_end + 1 >= pattern_len)
  213.           return 1;
  214.         else
  215.           ++suffix_end, ++prefix_end;
  216.       }
  217.  
  218.     /* This conditional expression is used to terminate the search when it
  219.        becomes clear that we can't match the PATTERN since the TEXT has
  220.        fewer unexamined characters than the PATTERN length. */
  221.     while (text_len - suffix_end >= pattern_len - prefix_end);
  222.  
  223.   else
  224.  
  225.     /* This loop is identical with the preceding one, except that we don't
  226.        bother to fold case... */
  227.  
  228.     do
  229.       {
  230.         while (prefix_end != RESET_PATTERN_FLAG 
  231.                && text[suffix_end] != pattern[prefix_end])
  232.           prefix_end = fail_trans_table[prefix_end];
  233.  
  234.         if (prefix_end + 1 >= pattern_len)
  235.           return 1;
  236.         else
  237.           ++suffix_end, ++prefix_end;
  238.       }
  239.     while (text_len - suffix_end >= pattern_len - prefix_end);
  240.  
  241.   return 0;
  242. }
  243.  
  244. /* The name sez it all! */
  245.  
  246. void
  247. print_usage_and_die (char *prog_name)
  248. {
  249.   fprintf (stderr, "usage: %s [-inv] pattern [file]\n", prog_name);
  250.   exit (1);
  251. }
  252.  
  253. /* Main driver program.  Emulates certain useful features of fgrep. */
  254.    
  255. int
  256. main (int argc, char **argv)
  257. {
  258.   GetOpt getopt(argc, argv, "dinv");
  259.  
  260.   if (argc == 1)
  261.     print_usage_and_die (argv[0]);
  262.  
  263.   /* A rather arbitrary limit... */
  264.   const int MAX_LINE = 200;
  265.   char  text[MAX_LINE];
  266.   int   c;
  267.       
  268.   /* Initialize any user-specified options. */
  269.  
  270.   while ((c = getopt ()) != EOF)
  271.     switch (c)
  272.       {
  273.       case 'd': option[DEBUG] = 1; break;
  274.       case 'i': option[FOLD_CASE] = 1; break;
  275.       case 'n': option[LINE_NUMBERS] = 1; break;
  276.       case 'v': option[INVERSE] = 1; break;
  277.       default:  print_usage_and_die (argv[0]);
  278.       }
  279.       
  280.   /* Call the constructor to build the failure function table. */
  281.   kmp match (argv[getopt.optind], strlen (argv[getopt.optind]), option[DEBUG]);
  282.  
  283.   /* Handle a user-specified input file. */
  284.   if (argv[++getopt.optind] && !freopen (argv[getopt.optind], "r", stdin))
  285.     {
  286.       perror (argv[0]); return 1;
  287.     }
  288.   
  289.   /* Split the following into two separate cases to avoid overhead 
  290.      when line numbers are not required. */
  291.   if (option[LINE_NUMBERS])
  292.     {
  293.       int line;
  294.       
  295.       for (line = 1; gets (text); line++)
  296.         if (match (text, strlen (text)) != option[INVERSE])
  297.           printf ("%d:%s\n", line, text);
  298.  
  299.     }
  300.   else
  301.     {
  302.  
  303.       while (gets (text))
  304.         if (match (text, strlen (text)) != option[INVERSE])
  305.           puts (text);
  306.  
  307.     }
  308.   return 0;
  309. }
  310.  
  311.